googologywikiaorg-20200223-history
Talk:Loader's number
I want to try to disassemble the program and figure out its value. Based on Meows' FGH comparison, it looks like it's at least on the tetrational array level. FB100Z • talk • 00:18, March 11, 2013 (UTC) Can we determine the order type of D(n)? Ikosarakt1 (talk ^ 12:38, April 3, 2013 (UTC) : Calculus of constructions is incredibly strong system. Theoretically, we can do it with every function. Practically, I think we don't have notations able to comprehend that ordinal. LittlePeng9 (talk) 13:13, April 3, 2013 (UTC) : I believe this is the fastest growing computable function ever defined, even faster than Bird's H(n). However, to comprehend its growth rate, I need to know first few terms of sequence. Do you know them? Ikosarakt1 (talk ^ 13:37, April 3, 2013 (UTC) : This function seems to have pretty slow start. D(99) is roughly power tower of height 30000, so calculating values of D(1), D(2) should be easy with loader.c with modified return value. Slow start is due to how program checks statements in CoC - it looks at statements with binary value = E(30416) = 2^^30416. Note the greater than or equals sign - I think that D(99) is probably much greater than 2^^30416. I tried running the program using Gnu C, for some reason I got D(2) = 65536, D(4) = 496, D(5) = 2031616, and negative values for other values of n. LittlePeng9's results are probably more accurate. ::@Ikosarakt1: I believe we can do better than the Calculus of Constructions by diagonolizing over a strong set theory like ZFC. For example, we can let \(f(n) = \sum_1^n g_i(n)\), where \(g_i(n)\) is the \(i\)th provably recursive function of ZFC. To compute \(f(n)\), we can search through all proofs of ZFC until we find a proof that a certain recursive function is total, set \(g_1\) to that function, and evaluate \(g_1\) at \(n\). Then repeat the procedure until we find \(n\) different functions, and sum all of them at \(n\). The resulting \(f(n)\) should grow faster than \(D(n)\). Deedlit11 (talk) 02:49, April 5, 2013 (UTC) ::Your results probably are wrong, because, if I understand definition correctly, D is monotonic. I must admit I had to modify loader.c a bit, because Visual C++ doesn't handle two functions reffering to each other very well. If you ask, I had to directly compute Apply within Subst function. LittlePeng9 (talk) 13:05, April 5, 2013 (UTC) :::I ran the program for higher values, and I also got D(8) = 496 and D(9) = 2031616, with "Segmentation fault" for D(10) and above. I guess the program just doesn't work properly for n < 8. It's interesting, though, that you get the same values for D(4) and D(5) as for D(8) and D(9). Deedlit11 (talk) 00:40, April 6, 2013 (UTC) ::::I know this is old topic, but the weird values are because int wraps around, even starting at D(0)=8‚646‚911‚284‚551‚352‚321. I and Nayuta Ito is evaluating D(0), D(1), D(2), and D(3) rn. πaruyoko (Talk) 02:08, August 31, 2019 (UTC) BB(160;7) vs. Loader's number to Deedlit11: I wrote that BB(160,7) more than Loader's number based on the your comment in LittlePeng's blog "Random Turing machines". Question of ikosarakt1: "Also notice that your machine is very probably not a busy beaver, so BB(160,7) can be incredibly large. So, is it true that BB(160,7)>>Loader's number?" Your answer: "@Ikosarakt1 Yes, I am pretty certain of it." Konkhra (talk) 05:08, May 6, 2013 (UTC) :But we are not sure. It might be a case that my machine is best Busy Beaver (not probable, but still). If we could compute D(n) in reasonable number of states, we would be sure. LittlePeng9 (talk) 12:48, May 6, 2013 (UTC) :Yeah, sorry for the confusion. My above answer was my personal opinion on the growth rate of the busy beaver (in fact, I believe that even BB(100,2) > Loader's number). But we shouldn't put it in the article unless we have proof that it is the case. Deedlit11 (talk) 22:34, May 6, 2013 (UTC) ::OK, I understand Konkhra (talk) 23:33, May 6, 2013 (UTC) Winner Congratulations! Loader! Your number are larger the BIGG :Again, why all the hate towards Hollom? FB100Z • talk • 04:29, May 30, 2013 (UTC) ::No? This number is bottom the bigg in the list. 04:44, May 30, 2013 (UTC) :::It's only our best guess. -- ☁ I want more ⛅ 13:35, May 30, 2013 (UTC) ::::Loader.c uses powerful and complex, but computable, system. I guess it is that large, though it still is guess. LittlePeng9 (talk) 18:29, May 30, 2013 (UTC) :::::Would this make it greater than Meameamealokkapoowa Oompa? 19:41, November 7, 2015 (UTC) ::::::Meameamealokkapoowa Oompa is not well-defined, so it can't be compared with other, well-defined numbers. LittlePeng9 (talk) 19:55, November 7, 2015 (UTC) :::::::Although even before all the debacle about the ill-definedness of meameamealokkapoowa oompa, Loader's number was generally considered to be larger than meameamealokkapoowa oompa. -- ☁ I want more ⛅ 02:16, November 8, 2015 (UTC) S function loses, still, because i see the SCG grows faster still, and the BIGG is below the SCG in the list. Jiawhien (talk) 11:20, May 31, 2013 (UTC) :BIGG is impressive because it's based on an array notation, and it reaches pretty far (we think). I mean, Buchholz hydras and subcubic graphs are really cool, but array notations reaching that far would be truly glorious. FB100Z • talk • 16:43, May 31, 2013 (UTC) ::I found that there exist two types of recursive functions: combinatorial (like SCG(n)) and explicit (like Bird's S(n)). The combinatorials are usually easy to define, but hard to solve. For example, proving even that \(n(3)\geq 64\) requires some effort, while value of S(3) can be quite easily in the FGH. Ikosarakt1 (talk ^ ) 19:25, May 31, 2013 (UTC) More Readable Code I've been working on making the code of the program a bit more readable (it couldn't really be any less readable in the original version). This is where I've got to (download link for txt file containing the code): loader_dot_c_readable_version.txt. This should make it a lot easier to analyse if you can actually see what it's doing! I've tested it for the values that actually work and I got the same as before the edit, so it should do the same thing.DrCeasium (talk) 18:45, June 1, 2013 (UTC) :Do you really understand how D(n) evaluates? If yes, maybe you can explain it less formally? Ikosarakt1 (talk ^ ) 19:34, June 1, 2013 (UTC) :Loader.c is actually standard, read-able program which was later mechanically compressed to 512-bit form. Here is full Loader's entry, containing every part of program, assembled one and compressed one, as well as README file being full explantation of how everything works. LittlePeng9 (talk) 19:55, June 1, 2013 (UTC) Theta function extensions We can define \(\theta_{\alpha+1}(0,\beta) = \theta_{\alpha}(\Omega_{\beta})\) and adopt the normal rules for theta function to higher order theta functions, then limit ordinal of all this will be the first alpha: \(\theta_{\alpha}(0) = \alpha\). Is there a chance that \(f_\alpha(n) \approx D(n)\)? Ikosarakt1 (talk ^ ) 13:19, June 18, 2013 (UTC) Nope, no chance. _Much_ stronger ordinal notations have been defined without going near the ordinal for higher order arithmetic. Deedlit11 (talk) 23:40, June 18, 2013 (UTC) Because the CoC can define second-order arithmetic, does that mean the proof-theoretic ordinal of CoC is larger than that of second-order arithmetic? --Ixfd64 (talk) 00:04, June 19, 2013 (UTC) :I don't think "CoC can define second-order arithmetic" is quite right - what is true is that CoC can define all provably recursive functions of second-order arithmetic. Since a type theory like CoC is quite different from the usual set theories for which proof theoretic ordinals are defined, we may need a different definition of "proof theoretic ordinal" for type theories. However, what we are concerned with are the definable functions of CoC, and since this contains all provably recursive functions of higher order arithmetic, we need to surpass all provably recursive ordinals of higher ordinal arithmetic to get to the level of D(n). Deedlit11 (talk) 01:01, June 19, 2013 (UTC) :Does that mean that its practically impossible to reach CoC level using an array notation or countable ordinal notation that uses only recursion and similar methods? DrCeasium (talk) 17:39, June 22, 2013 (UTC) :Maybe the very, very sophicticated array notation with complex 100 rules or so, can reach it, but since we haven't the recursive notation for Loader's ordinal, I can't be sure. Ikosarakt1 (talk ^ ) 09:00, June 23, 2013 (UTC) ::It's not theoretically impossible, but professional mathematicians, who have stronger guiding principles to work with, have not been able to reach it, so I don't think it's likely that one of us will. Of course, if the notations become strong enough it may become difficult to tell. Deedlit11 (talk) 10:21, June 24, 2013 (UTC) :::Someone claims to have a notation capable of reaching second-order arithmetic. I have no idea if it really does. --Ixfd64 (talk) 16:01, June 24, 2013 (UTC) :::It is so hard to understand. Ikosarakt1 (talk ^ ) 16:09, June 24, 2013 (UTC) Values I ran the program through manually for D(1), and I think the reason we,be been getting strange results is that even this is (just) overflowing the storage for an int: the way the pair function works is pretty powerful in comparison to the size of an int. Another reason why it may be broken is that I can't see anywhere where accumulate is actually given a value, until it is defined as pair(some stuff,accumulate), either I'm too used to Java, or that won't work properly. DrCeasium (talk) 08:47, June 23, 2013 (UTC) How high the max value of your int type? I guess that 2147483647. Ikosarakt1 (talk ^ ) 09:00, June 23, 2013 (UTC) Using unsigned int we can reach 2^32-1, but by using unsigned long long int we can reach up to 2^64-1. LittlePeng9 (talk) 09:11, June 23, 2013 (UTC) Just checked: I actually meant D(0) overflowed the int value, as it was at least 16 billion. D(1) was > 10^10^10, and I don't think there are any ints that big. There is still the problem of the undefined accumulate, as that could probably change the output too. (This isn't just me with the undefined accumulate is it?) DrCeasium (talk) 10:12, June 23, 2013 (UTC) Just ran the program in debug, and I found that D(0) just about worked and outputted 2013265921. D(1) had a final value of pair(1006632960,2013265921) = 2013265921*(2^(1006632960)). Also, if D(k) just adds up all of the bit strings of binary value k or lower (assuming a bit string is a string of bits eg10110, and its binary value is its value in binary, in this case 2+4+16 = 22), that really doesn't sound that powerful, and even if instead of adding you just stick them on the end of each other, so for example 1011+1001 = 10111001, that still doesn't sound like 'biggest computable number ever' big. I'm not saying it's not the biggest computable number ever, but the description doesn't make it sound that big at all. DrCeasium (talk) 18:14, June 23, 2013 (UTC) If I'm not mistaken Loader's program works like this: it takes lambda expression with value less than k, normalises it (reduces to normal form, which may be represented by large integer) and sums all these normalised forms. If we translate CoC to higher order logic, Loader explains how large approximately it gets: "Let N be the base 2 log of the argument of Derive. Suppose that Higher Order Arithmetic can prove a closed Sigma^0_1-arithemetic statment "Exists(x) phi(x)", with a proof not longer than N. Then "Derive(N)" returns a number larger than the smallest x such that phi(x)." LittlePeng9 (talk) 18:30, June 23, 2013 (UTC) :Bun even first order arithmetic has level \(\omega_\omega^\text{CK}\), so how D(n) can be computable? Ikosarakt1 (talk ^ ) 18:34, June 23, 2013 (UTC) :The uncomputable functions are strange, because they are, in a sense, computable, because we can work out the lower values by going through every possible start and applying intelligence, which would suggest that a sufficiently powerful, and almost intelligent computer could work them out too. In fact, it is easy to cycle through all possible start values for most of these things, the hard part is just picking out the infinities. Maybe this is just an uncomputable function without any infinities that need removing, and so is sort of computable. DrCeasium (talk) 18:58, June 23, 2013 (UTC) :Uncomputable functions are uncomputable, no worry about it. But every finite subset of values is computable. In fact, given any finite ordered multiset of numbers {a1,a2,...,an} there is polynomial such that p(x)-ax. As far as Church-Turing thesis is true, we can't compute uncomputable function in finite time. :Point with higher order logic in CoC is that CoC captures recursive ''part of HOL, by which I mean every provably recursive (i.e. computable) function in HOL is expressible in CoC. This is how Derive(n) is computable. LittlePeng9 (talk) 19:04, June 23, 2013 (UTC) \(\Sigma(160) >\) Loader's number Even though it seems reasonable, I haven't seen the proof for the statement above. Can anyone point me on that? Ikosarakt1 (talk ^ ) 19:02, September 26, 2013 (UTC) We don't have a proof, this is a statement we once concluded to be very likely, while discussing my bound of BB(160,7)>>Bird's N. I think this should be deleted. LittlePeng9 (talk) 19:30, September 26, 2013 (UTC) More Values In the section above I found D(0) = 2013265921 and D(1) = \(2013265921 \cdot 2^{1006632960}\). Can we find more values. Also, I think we should put these values in the article. Wythagoras (talk) 16:05, October 20, 2013 (UTC) Everyone can try to find these values. But I think there is something wrong here - if D(n) uses strings with binary values at most n, then only string for D(0) would be 0, which almost certainly codes no proof. Same goes with D(1). I did not analyse program carefully enough to be sure, but it sounds a bit silly that D(0) codes proof giving number about 2 billion. LittlePeng9 (talk) 16:30, October 20, 2013 (UTC) :I'm also a bit skeptical about these values. I think the numbers obtained by Deedlit11 and LittlePeng9 are more accurate. --Ixfd64 (talk) 22:43, October 20, 2013 (UTC) Programs If CoC is indeed the programming language, then if we want to be sure that f(n) < D(n), we just write down the program for f(n) on CoC. Some sort of ruleset is presented here, but I can't extract even how to make f(n) = n+1 from such rules. Ikosarakt1 (talk ^ ) 05:48, June 24, 2014 (UTC) :I wouldn't call CoC a programming language, but it still can be thought of as one. Creating "simple" functions in this system is, I believe, in principle the same as in full lambda calculus, except it's a bit more work to get types right (I'm not an expert though). LittlePeng9 (talk) 10:44, June 24, 2014 (UTC) Date What's the date of Bignum Bakeoff? Ikosarakt1 (talk ^ ) 12:25, July 12, 2014 (UTC) : December 2001, source. LittlePeng9 (talk) 12:51, July 12, 2014 (UTC) ::More precisely, it began on Dec 10 and ended on Dec 31. -- ☁ I want more ⛅ 12:53, July 12, 2014 (UTC) ::Thanks. I wonder why it wasn't in the scope of googology until 2013. Ikosarakt1 (talk ^ ) 13:03, July 13, 2014 (UTC) To vel! : Says the "List of googological Functions" page. \(\ Antares.H \) 07:17, March 23, 2015 (UTC) :Not quite, the list of googological functions page states that the function is lower-bounded by f_whatever(n) whereas the article states a ''specific growth rate. (To say nothing of the fact that the choice of fundamental sequence systems is not specified) -- ve 08:02, March 23, 2015 (UTC) :I believe we should suppose standard FS-es unless otherwise specified. Ikosarakt1 (talk ^ ) 09:24, March 23, 2015 (UTC) ::There are no "standard" FS's for ordinals that large, or at least I'm not aware of existence of such. LittlePeng9 (talk) 10:40, March 23, 2015 (UTC) ::In that case, I think it's fair to say that Loader's function is above all so-far defined functions in FGH. Ikosarakt1 (talk ^ ) 06:01, March 24, 2015 (UTC) :::FGH has been extended to \(\omega_1^\text{CK}\) and even further, so I guess it's too much to say that Loader's function beats all of it. LittlePeng9 (talk) 14:11, March 24, 2015 (UTC) BB(106) isn't enough I compiled loader.c and this is the output ASM file: http://pastebin.com/R1X24EM5 It takes 514 instructions in ASM, so I don't see how a busy-beaver with only 106 instructions could go faster than this. I think the value for which BB(n) start outgrowing D(n) is much higher than 106 =/ Fluoroantimonic Acid (talk) 07:39, June 29, 2015 (UTC) : As I have told you on the chat, this isn't any kind of proof. I am willing to agree that 106 states (which amounts to 312, not 106 instructions of a TM) might not be enough, basing that just on the number of instructions compared to the ASM code tells us nothing. It might be the case that a TMs can use what they have in more effective way, so they can give larger outputs with less instructions. This is most likely the case for small number of instructions - I don't know how large input you can get with 14 instructions in ASM, but 14 instructions in TM are enough for \(10\uparrow\uparrow 5\). LittlePeng9 (talk) 07:55, June 29, 2015 (UTC) :With 312 instructions, it's very likely that we can define Universal Turing machines... 14:20, November 8, 2015 (UTC) ::There are 2-color Turing machines with as few as 15 states, or 30 transitions. LittlePeng9 (talk) 14:42, November 8, 2015 (UTC) Growth rate How can \(D(n)\) grow so fast? Are there any lower bounds for it and can it be compared to the FGH?Boboris02 (talk) 09:55, October 30, 2016 (UTC) What is the difference between Turing machines and C programs? Loader's number and its properties I factored the result numbers of Deedlit11 and LittlePeng9 and managed to get this: D(8) = 496 = 16 * 31 = 2^^3 * 31; D(9) = 2031616 = 65536 * 31 = 2^^4 * 31. Conjecture 1: all following values of D function are divisible by 31 and result after dividing D(n) by 31 is some tetration of 2. Therefore, Loader's number ends in 6. Conjecture 2: D(n) >= 2^^(n-5) * 31. It would be interesting to compute D(10) and verify these conjectures. Tetramur (talk) 11:39, January 17, 2020 (UTC) : If conjecture 1 is true, then that would imply that the last 20 digits of Loader's number are ...57,067,335,956,421,410,816. Assuming conjecture 2, D(10) > 31*2^^5 ~ 6.2109*10^19729, which would explain why that's where other users here ran into problems. Of course, there has been disagreement over the values of the D function (for instance, another user obtained 2013265921 or 15*2^27 + 1 as the value of D(0) and D(1) ~> 2^10^9. Allam948736 (talk) 22:22, January 17, 2020 (UTC)